import struct

def compressMethod(lsbs: list[str])->bytes:
    """
    使用 RLE + Delta 编码压缩二进制序列
    :param lsbs: 字符 '0' 和 '1' 组成的列表
    :return: 压缩后的字节数据
    """
    if not lsbs:
        return b''

    lsbsStr = ''.join(lsbs)

    # === 1. RLE 编码：提取 (bit, count) ===
    rle = []
    current_bit = lsbsStr[0]
    count = 1

    for bit in lsbsStr[1:]:
        if bit == current_bit:
            count += 1
        else:
            rle.append((current_bit, count))
            current_bit = bit
            count = 1
    rle.append((current_bit, count))

    # print(f"RLE 结果: {rle}")

    # === 2. 提取长度序列，进行 Delta 编码 ===
    lengths = [cnt for bit, cnt in rle]
    # print(f"原始长度序列: {lengths}")

    # Delta 编码：delta[i] = lengths[i] - lengths[i-1]
    delta_lengths = []
    for i in range(len(lengths)):
        if i == 0:
            delta_lengths.append(lengths[i])  # 第一个值原样保存
        else:
            delta = lengths[i] - lengths[i-1]
            delta_lengths.append(delta)

    # print(f"Delta 编码后长度: {delta_lengths}")

    # === 3. 打包成字节流 ===
    # 格式：
    # - 起始比特 (1 byte)
    # - 条目数 (4 bytes, uint32)
    # - 每个 Delta 值用 4 字节带符号整数（int32）存储
    bit_start = 0 if rle[0][0] == '0' else 1
    n_entries = len(delta_lengths)

    # 打包
    data = struct.pack('<BI', bit_start, n_entries)  # 起始比特 + 个数
    for delta in delta_lengths:
        data += struct.pack('<i', delta)  # i: 有符号 32 位整数

    compressed_bytes = data

    # === 4. 原始数据大小（用于对比）===
    def bin_str_to_bytes(s):
        padded = s.ljust((len(s) + 7) // 8 * 8, '0')
        return bytes([int(padded[i:i+8], 2) for i in range(0, len(padded), 8)])

    original_bytes = bin_str_to_bytes(lsbsStr)
    original_size = len(original_bytes)
    compressed_size = len(compressed_bytes)

    # print(f"Delta 压缩前: {original_size} 字节")
    # print(f"Delta 压缩后: {compressed_size} 字节")
    # ratio = compressed_size / original_size if original_size > 0 else 0
    # print(f"压缩比: {ratio:.2f}")

    return compressed_bytes


def decompressWithDelta(compressed_data: bytes, total_bits: int = None)-> list[str]:
    """
    解压 Delta 编码的数据
    :param compressed_data: 压缩后的字节
    :param total_bits: 原始比特总数（可选，用于截断）
    :return: 解压后的比特列表
    """
    if len(compressed_data) < 5:
        raise ValueError("压缩数据过短")

    # 解包头部
    bit_start = struct.unpack('<B', compressed_data[0:1])[0]
    n_entries = struct.unpack('<I', compressed_data[1:5])[0]
    delta_data = compressed_data[5:]

    if len(delta_data) < n_entries * 4:
        raise ValueError("数据长度不足")

    # 提取 Delta 序列
    delta_lengths = []
    for i in range(n_entries):
        delta = struct.unpack('<i', delta_data[i*4:(i+1)*4])[0]
        delta_lengths.append(delta)

    # Delta 解码 → 原始长度
    lengths = []
    for i, delta in enumerate(delta_lengths):
        if i == 0:
            lengths.append(delta)
        else:
            lengths.append(lengths[i-1] + delta)

    # RLE 解码
    current_bit = '0' if bit_start == 0 else '1'
    result = []
    for i, cnt in enumerate(lengths):
        bit_char = '1' if current_bit == '1' else '0'
        result.append(bit_char * cnt)
        current_bit = '1' if current_bit == '0' else '0'  # 切换

    reconstructed = ''.join(result)

    if total_bits is not None:
        reconstructed = reconstructed[:total_bits]

    return list(reconstructed)


# === 示例使用 ===
if __name__ == "__main__":
    # 示例：交替游程，长度缓慢变化
    lsbs = (
        ['0'] * 10 +
        ['1'] * 12 +
        ['0'] * 15 +
        ['1'] * 18 +
        ['0'] * 20 +
        ['1'] * 19 +
        ['0'] * 18
    )

    print("=== Delta 编码压缩 ===")
    compressed = compressMethod(lsbs)

    print("\n=== Delta 解压测试 ===")
    decompressed = decompressWithDelta(compressed, total_bits=len(lsbs))

    if decompressed == lsbs:
        print("✅ 解压成功，数据一致！")
    else:
        print("❌ 解压失败！")